ICPC Live Archive/3927 - Ambiguous Codes/3927.cpp

   1 // Andrés Mejía
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 const double EPS = 1e-9;
  29 int cmp(double x, double y = 0, double tol = EPS) {
  30     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  31 }
  32
  33 const int MAXN = 105, MAXL = 55, oo = 1 << 28;
  34 string words[MAXN];
  35 int dist[MAXN][MAXL];
  36 int n;
  37
  38 long long pack(int index, int behind, int weight) {
  39     return ((long long)weight << 16L) + (behind << 8L) + index;
  40 }
  41
  42 void unpack(long long state, int &index, int &behind, int &weight) {
  43     index = state & 255L;
  44     state >>= 8L;
  45     behind = state & 255L;
  46     state >>= 8L;
  47     weight = state;
  48 }
  49
  50 inline bool isPrefix(const string &a, const string &b) {
  51     if (a.size() > b.size()) return false;
  52     for (int i = 0; i < a.size(); ++i) {
  53         if (a[i] != b[i]) return false;
  54     }
  55     return true;
  56 }
  57
  58
  59 int search() {
  60     for (int i = 0; i < n; ++i) {
  61         for (int d = 0; d < MAXL; ++d) {
  62             dist[i][d] = oo;
  63         }
  64     }
  65
  66     priority_queue<long long, vector<long long>, greater<long long> > q;
  67     for (int i = 0; i < n; ++i) {
  68         for (int j = 0; j < n; ++j) {
  69             if (i == j) continue;
  70             if (isPrefix(words[j], words[i])) {
  71                 assert(words[j].size() < words[i].size());
  72                 int diff = words[i].size() - words[j].size();
  73                 dist[i][diff] = words[i].size();
  74                 long long state = pack(i, diff, dist[i][diff]);
  75                 q.push(state);
  76             }
  77         }
  78     }
  79
  80     while (q.size() > 0) {
  81         long long state = q.top(); q.pop();
  82         int index, behind, weight;
  83         unpack(state, index, behind, weight);
  84         //printf("Popped state <i=%d, d=%d> (%s, %s) with weight w=%d\n", index, behind,  words[index].c_str(), words[index].substr(0, words[index].size() - behind).c_str(),  weight);
  85         if (behind == 0) {
  86             return weight;
  87         }
  88         if (weight > dist[index][behind]) continue;
  89
  90         const string tail = words[index].substr(words[index].size() - behind);
  91         //printf("  Tail is %s\n", tail.c_str());
  92         assert(tail.size() == behind);
  93
  94         for (int k = 0; k < n; ++k) {
  95             //printf("  Trying words[k=%d] = %s\n", k, words[k].c_str());
  96             if (words[k].size() - behind >= 0 and isPrefix(tail, words[k]) ) {
  97                 int new_index = k;
  98                 int new_behind = words[new_index].size() - behind;
  99                 int new_weight = weight + new_behind;
 100                 //printf("   Option 1: Can reach state <i=%d, d=%d> (%s, %s) with weight = w=%d\n", new_index, new_behind, words[new_index].c_str(), words[new_index].substr(0, words[new_index].size() - new_behind).c_str(), new_weight );
 101                 if (new_weight < dist[new_index][new_behind]) {
 102                     dist[new_index][new_behind] = new_weight;
 103                     q.push( pack(new_index, new_behind, new_weight) );
 104                     //printf("   That's better.\n");
 105                 }
 106             }
 107
 108             if (behind - words[k].size() >= 0 and isPrefix(words[k], tail) ) {
 109                 int new_index = index;
 110                 int new_behind = behind - words[k].size();
 111                 int new_weight = weight + 0;
 112                 //printf("   Option 2: Can reach state <i=%d, d=%d> (%s, %s) with weight = w=%d\n", new_index, new_behind, words[new_index].c_str(), words[new_index].substr(0, words[new_index].size() - new_behind).c_str(), new_weight );
 113                 if (new_weight < dist[new_index][new_behind]) {
 114                     dist[new_index][new_behind] = new_weight;
 115                     q.push( pack(new_index, new_behind, new_weight) );
 116                     //printf("   That's better.\n");
 117                 }
 118             }
 119         }
 120
 121     }
 122     return -1;
 123 }
 124
 125 int main(){
 126     while (cin >> n) {
 127         if (n == 0) break;
 128         for (int i = 0; i < n; ++i) cin >> words[i];
 129         int ans = search();
 130         cout << ans << endl;
 131     }
 132     return 0;
 133 }